/**
 * ClassName: main
 * Package: PACKAGE_NAME
 * Description:
 *
 * @Author Li
 * @Create 2024/11/3 15:43
 * @Version 1.0
 */
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main {
    public static void main(String[] args) {
//        int[] arr = {1,2,1};
//        int[] arr2 = {2,3,2,3,2};
//        int[] solve = solve2(arr);
//        int[] solve2 = solve2(arr2);

        int[] arr3 = {1,1,2,2,1};
        int bamiao = bamiao(arr3);
        int bamiao2 = bamiao2(arr3);
        System.out.print(bamiao);
        System.out.print(bamiao2);

//        System.out.print(Arrays.toString(solve));
//        System.out.print(Arrays.toString(solve2));
    }

//    public static int[] solve (int[] arr) {
//        HashMap<Integer, List<Integer>> groups = new HashMap<>();
//
//        for(int i=0;i<arr.length;i++) {
//            int presonid = i + 1;
//            int groupid = arr[i];
//            if (!groups.containsKey(groupid)) {
//                groups.put(groupid, new ArrayList<>());
//            }
//
//            groups.get(groupid).add(presonid);
//        }
//
////            List<int[]> cppairs = new ArrayList<>();
//
//
//            int[] result = new int[arr.length];
//            Arrays.fill(result,-1);
//
//            int cpid=1;
//        for(Map.Entry<Integer,List<Integer>> entry : groups.entrySet()){
//            List<Integer> members =entry.getValue();
//            if(members.size()==2){
//                result[members.get(0)-1] =
//                int[] pair = {members.get(0),members.get(1)};
//                cppairs.add(pair);
//            }
//        }
//        return result;// write code here
//    }

    public static int[] solve2 (int[] arr) {
        HashMap<Integer, List<Integer>> groupmap = new HashMap<>();

        for(int i=0;i<arr.length;i++) {
            groupmap.putIfAbsent(arr[i],new ArrayList<>());
            groupmap.get(arr[i]).add(i+1);
        }

        int[] result = new int[arr.length];
        Arrays.fill(result,-1);

        for (List<Integer> members :groupmap.values()){
            if (members.size()==2){
                int person1 = members.get(0);
                int person2 = members.get(1);

                result[person2-1] =person1;
                result[person1-1] = person2;
            }
        }
        return result;

    }

    public static int bamiao(int[] heights) {
        int left = 0;
        int right = heights.length - 1;
        int operation = 0;
        while (left < right) {
            if (heights[left] != heights[right]) {

                while (heights[left] != heights[right]) {
                    if (heights[left] < heights[right]) {
                        heights[left]++;
                        heights[left+1]++;

                    } else {
                        heights[right]++;
                        heights[right- 1]++;
                    }
                    operation++;
                    if(operation >1000){
                        return -1;
                    }

                }

            }
            left++;
            right--;
        }
        return operation;
    }



    public static int bamiao2(int[] a) {
        int n = a.length;
        int[][]dp =new int[n][n];

        for (int i =0;i<n;i++){
            for(int j=0;j<n;j++){
                dp[i][j]=-1;
            }
        }

        return bam(a,0,n-1,dp);


//
//        for(int len=2;len<=n;len++){
//            for(int i=0;i<=n-len;i++){
//                int j=i+len-1;
//                if(a[i] ==a[j]){
//                    dp[i][j]=dp[i+1][j-1];
//                }else {
//                    dp[i][j] = Math.min(dp[i+1][j]+(a[j]-a[i]),dp[i][j-1]+(a[i]-a[j]));
//                }
//            }
//        }
//        return dp[0][n-1];

    }

    private static int bam(int[] a, int i, int j, int[][] dp) {
        if(i>=j){
            return 0;

        }


        if(dp[i][j] != -1) return dp[i][j];

        if(a[i]==a[j]){
            dp[i][j] =bam(a,i+1,j-1,dp);

        }else {
            int increleft =bam(a,i+1,j,dp)+(a[j]-a[i]);
            int increright = bam(a,i,j-1,dp)+(a[i]-a[j]);
            dp[i][j] =Math.min(increleft,increright);
        }
        return  dp[i][j];

    }
}